// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package jpeg

import (
	"io"
)

// maxCodeLength是哈夫曼码中的最大（含）位数。
const maxCodeLength = 16

// maxNCodes是哈夫曼树中的最大（含）代码数。
const maxNCodes = 256

// lutSize是哈夫曼解码器查找表的log-2大小。
const lutSize = 8

// 哈夫曼是一个哈夫曼解码器，在C节中指定。
type huffman struct {
	// 长度是树中的代码数。
	nCodes int32
	// lut是位流中下一个lutSize位的查找表。
	// uint16的高8位是编码值。低8位
	// 为1加上代码长度，如果值太大，无法放入
	// lutSize位，则为0。
	lut [1 << lutSize]uint16
	// VAL是按编码排序的解码值。
	vals [maxNCodes]uint8
	// 最小代码[i]是长度为i的最小代码，如果没有该长度的
	// 代码，则为-1。
	minCodes [maxCodeLength]int32
	// maxCodes[i]是长度i的最大代码，如果没有该长度的
	// 代码，则为-1。
	maxCodes [maxCodeLength]int32
	// ValsIndexes[i]是最小码[i]的VAL索引。
	valsIndices [maxCodeLength]int32
}

// errShortHuffmanData表示解码
// Huffman数据时发生意外的EOF。
var errShortHuffmanData = FormatError("short Huffman data")

// ensureNBits从字节缓冲区读取字节，以确保d.bits。n是
// 至少是n。为了获得最佳性能（避免在热循环中调用函数），
// 首先检查d位的是调用方。n<n.
func (d *decoder) ensureNBits(n int32) error {
	for {
		c, err := d.readByteStuffedByte()
		if err != nil {
			if err == io.EOF {
				return errShortHuffmanData
			}
			return err
		}
		d.bits.a = d.bits.a<<8 | uint32(c)
		d.bits.n += 8
		if d.bits.m == 0 {
			d.bits.m = 1 << 7
		} else {
			d.bits.m <<= 8
		}
		if d.bits.n >= n {
			break
		}
	}
	return nil
}

// receiveExtend是第
// F.2.2.1节规定的接收和扩展的组成部分。
func (d *decoder) receiveExtend(t uint8) (int32, error) {
	if d.bits.n < int32(t) {
		if err := d.ensureNBits(int32(t)); err != nil {
			return 0, err
		}
	}
	d.bits.n -= int32(t)
	d.bits.m >>= t
	s := int32(1) << t
	x := int32(d.bits.a>>uint8(d.bits.n)) & (s - 1)
	if x < s>>1 {
		x += ((-1) << t) + 1
	}
	return x, nil
}

// processDHT处理Define Huffman表标记，并根据其内容初始化Huffman 
// struct。第B.2.4.2节中规定。
func (d *decoder) processDHT(n int) error {
	for n > 0 {
		if n < 17 {
			return FormatError("DHT has wrong length")
		}
		if err := d.readFull(d.tmp[:17]); err != nil {
			return err
		}
		tc := d.tmp[0] >> 4
		if tc > maxTc {
			return FormatError("bad Tc value")
		}
		th := d.tmp[0] & 0x0f
		// 表B.5规定了基线th<=1限制。
		if th > maxTh || (d.baseline && th > 1) {
			return FormatError("bad Th value")
		}
		h := &d.huff[tc][th]

		// 读取NCODE和h.VAL（并导出h.NCODE）。
		// nCodes[i]是代码长度为i的代码数。
		// h.nCodes是代码总数。
		h.nCodes = 0
		var nCodes [maxCodeLength]int32
		for i := range nCodes {
			nCodes[i] = int32(d.tmp[i+1])
			h.nCodes += nCodes[i]
		}
		if h.nCodes == 0 {
			return FormatError("Huffman table has zero length")
		}
		if h.nCodes > maxNCodes {
			return FormatError("Huffman table has excessive length")
		}
		n -= int(h.nCodes) + 17
		if n < 0 {
			return FormatError("DHT has wrong length")
		}
		if err := d.readFull(h.vals[:h.nCodes]); err != nil {
			return err
		}

		// 导出查找表。
		for i := range h.lut {
			h.lut[i] = 0
		}
		var x, code uint32
		for i := uint32(0); i < lutSize; i++ {
			code <<= 1
			for j := int32(0); j < nCodes[i]; j++ {
				// 码长为1+i，因此将code移位8-（1+i）到
				// 计算每个8位序列的高位
				// 其码长的高位与code匹配。
				// lutValue的高8位是编码值。
				// 低8位是1加上码长。
				base := uint8(code << (7 - i))
				lutValue := uint16(h.vals[x])<<8 | uint16(2+i)
				for k := uint8(0); k < 1<<(7-i); k++ {
					h.lut[base|k] = lutValue
				}
				code++
				x++
			}
		}

		// 导出minCodes、maxCodes和ValsIndex。
		var c, index int32
		for i, n := range nCodes {
			if n == 0 {
				h.minCodes[i] = -1
				h.maxCodes[i] = -1
				h.valsIndices[i] = -1
			} else {
				h.minCodes[i] = c
				h.maxCodes[i] = c + n - 1
				h.valsIndices[i] = index
				c += n
				index += n
			}
			c <<= 1
		}
	}
	return nil
}

// 解码哈夫曼返回位流中的下一个哈夫曼编码值，
// 根据h解码。
func (d *decoder) decodeHuffman(h *huffman) (uint8, error) {
	if h.nCodes == 0 {
		return 0, FormatError("uninitialized Huffman table")
	}

	if d.bits.n < 8 {
		if err := d.ensureNBits(8); err != nil {
			if err != errMissingFF00 && err != errShortHuffmanData {
				return 0, err
			}
			// 此段中没有更多字节的数据，但我们仍然可以从之前读取的位中读取下一个符号。
			// 首先，撤消EnsureBits调用的readByte。
			if d.bytes.nUnreadable != 0 {
				d.unreadByteStuffedByte()
			}
			goto slowPath
		}
	}
	if v := h.lut[(d.bits.a>>uint32(d.bits.n-lutSize))&0xff]; v != 0 {
		n := (v & 0xff) - 1
		d.bits.n -= int32(n)
		d.bits.m >>= n
		return uint8(v >> 8), nil
	}

slowPath:
	for i, code := 0, int32(0); i < maxCodeLength; i++ {
		if d.bits.n == 0 {
			if err := d.ensureNBits(1); err != nil {
				return 0, err
			}
		}
		if d.bits.a&d.bits.m != 0 {
			code |= 1
		}
		d.bits.n--
		d.bits.m >>= 1
		if code <= h.maxCodes[i] {
			return h.vals[h.valsIndices[i]+code-h.minCodes[i]], nil
		}
		code <<= 1
	}
	return 0, FormatError("bad Huffman code")
}

func (d *decoder) decodeBit() (bool, error) {
	if d.bits.n == 0 {
		if err := d.ensureNBits(1); err != nil {
			return false, err
		}
	}
	ret := d.bits.a&d.bits.m != 0
	d.bits.n--
	d.bits.m >>= 1
	return ret, nil
}

func (d *decoder) decodeBits(n int32) (uint32, error) {
	if d.bits.n < n {
		if err := d.ensureNBits(n); err != nil {
			return 0, err
		}
	}
	ret := d.bits.a >> uint32(d.bits.n-n)
	ret &= (1 << uint32(n)) - 1
	d.bits.n -= n
	d.bits.m >>= uint32(n)
	return ret, nil
}
